package lc.Q200_250;

import lc.TreeNode;

/**
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 *
 * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
 */
public class Q222 {
    public int countNodes(TreeNode root) {
        // 根据定义，只有最底层可能为空，那么范围就是[2^(n-1),2^n-1]
        // 查找层数，只数左边
        if (root == null) return 0;
        int level = 0;
        TreeNode left = root;
        while (left.left != null) {
            level += 1;
            left = left.left;
        }
        // 注意level从0开始
        // 数最底层的个数
        int low = 1 << level;
        int high = (1 << (level + 1)) - 1;
        // 叶子节点
        while (low < high) {
            // 算mid，如果存在在往右边找，不存在往左边找
            int mid = (high - low + 1) / 2 + low;
            if (exist(root,level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;

    }

    public boolean exist(TreeNode root,int level, int i) {
        // 判断存在方式
        // 先判断i应该在左节点还是右节点，根据规律,i的二进制位第二位（从高位数）为0在左边，为1在右边，然后依次
        int bits = 1 << (level - 1);
        TreeNode node = root;
        while (node != null && bits > 0) {
            if ((bits & i) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;

    }
}
